import org.junit.Test;

import java.util.HashMap;

public class FibonacciSequence {
    @Test
    public void clibe() {
        long n = 10;

        //无缓存结果

        long startTime1 =  System.currentTimeMillis();
        long i = testClimb(n);
        long endTime1 =  System.currentTimeMillis();
        System.out.println("无缓存结果:"+i+",使用时间:"+ (endTime1-startTime1));

        //有缓存结果
        long startTime2 =  System.currentTimeMillis();
        long a = testClimbByCache(n);
        long endTime2 =  System.currentTimeMillis();
        System.out.println("有缓存结果:"+a+",使用时间:"+ (endTime2-startTime2));

        //经过循环结果
        long startTime3 =  System.currentTimeMillis();
        long b = testClimbByFor(n);
        long endTime3 =  System.currentTimeMillis();
        System.out.println("循环结果:"+b+",使用时间:"+ (endTime3-startTime3));
    }

    /**
     * 递归:无缓存,格式
     * @param n
     * @return
     */
    private long testClimb(long n) {
        if (n==0) return 0;
        if (n==1 || n==2) return 1;
        return testClimb(n-2)+testClimb(n-1);
    }

    /**
     * 添加缓存
     */
    HashMap<Long,Long> cacheMap = new HashMap<Long, Long>();
    private long testClimbByCache(long n) {

        if (n==0) return 0;
        if (n==1 || n==2) return 1;
        if (null != cacheMap.get(n)){
            return cacheMap.get(n);
        }else {
            long resultByCache=testClimbByCache(n-2)+testClimbByCache(n-1);
            cacheMap.put(n,resultByCache);
            return resultByCache;
        }
    }

    /**
     * 使用循环实现
     * @param n
     * @return
     */
    private long testClimbByFor(long n){
        if (n==0) return 0;
        if (n==1 || n==2) return 1;

        long pre = 1;
        long prepre = 1;
        long result = 0;

        for (long i = 3; i <= n; ++i) {
            result = pre + prepre;
            prepre = pre;
            pre = result;
        }
        return result;
    }
}
